package com.example.system.class22;

/**
 * @Date 2022/8/21
 * @Author Jonathan
 * @Description 左上到右下的和最小
 * </p>
 * 本题是经典的动态规划题目
 * 优化点：空间压缩技巧
 */
public class Code01_MinPathSum {
    public static void main(String[] args) {

    }


    public static int minPathSum(int[][] m) {
        int row = m.length;
        int col = m[0].length;
        int[][] dp = new int[row][col];
        dp[0][0] = m[0][0];
        for (int i = 1; i < row; i++) {
            dp[i][0] = dp[i - 1][0] + m[i][0];
        }
        for (int i = 1; i < col; i++) {
            dp[0][i] = dp[0][i - 1] + m[0][i];
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + m[i][j];
            }
        }

        return dp[row - 1][col - 1];
    }

    // TODO  辅助空间改成一维的
    public static int minPathSum2(int[][] m) {

        return 0;
    }

}
